package com.github.hgkmail.hello.leetcode101.dp;

public class LC70ClimbingStairs {
    public int helper(int n, int[] memo) {
        if (n==1) return 1; //1个台阶只有一种
        if (n==2) return 2; //2个台阶有2种，1步+1步，或者直接2步
        //是否已经算过了
        if (memo[n]>0) return memo[n];
        //计算，可以退1步，也可以退2步
        memo[n]=helper(n-1, memo)+helper(n-2, memo);

        return memo[n];
    }
    public int climbStairs(int n) {
        int[] memo = new int[n+1];
        for (int i = 0; i < memo.length; i++) {
            memo[i]=0;
        }
        int res = helper(n, memo);
        return res;
    }
    public static void main(String[] args) {
        System.out.println(new LC70ClimbingStairs().climbStairs(10));
    }
}
